public class MedianFinder {
    /**
     * 1、需要一个数据结构来存储这个数
     * 2、每次存储完不能直接进行排序
     *
     */
    int N = 5001; //数组最大长度
    int[] nums; //存储进去的数组
    int n; //数组现有元素个数
    double mid_num;  //中位数
    int loc;//中位数目前存在的位置
    public MedianFinder() {
         nums = new int[N];
         n = 0;
    }

    public void addNum(int num) {
        if (n==0){
            nums[0]  =num;
            mid_num = num;
            loc = 0;
        }else {
            //先用二分找到这个数字的位置
            int low =0;
            int right = n-1;
            int  mid = low+(right-low)/2;
            while (low<=right){
                if (nums[mid]==num){
                    break;
                }
                else if (nums[mid]<num){
                    right = mid-1;
                }else {
                    low = mid +1;
                }
                 mid = low+(right-low)/2;
            }
            //从mid位置开始，所有元素后移一位;
            for (int i=n+1;i>=mid;i--){
                nums[i+1] = nums[i];
            }
            nums[mid] = num;
            if (n%2==0){
                mid_num = nums[(n+1)/2];
            }else {
                mid_num = (nums[(n+1)/2] +nums[(n+1)/2-1])/2.0;
            }

        }
        n++;
    }

    public double findMedian() {
        return mid_num;
    }

}
